package lecode01;



/**
 * 示例
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 */
public class 两两交换链表中的节点24 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4,new ListNode(5)))));
//        System.out.println(iteratePairs(l1).toString());
        System.out.println(swapPairs(l1).toString());
    }

    /**
     * 迭代法
     */
    public static ListNode iteratePairs(ListNode head) {
        //前置判断
        if (head == null || head.next == null) {
            return head;
        }

        //构建一个临时节点
        ListNode res = new ListNode();
        //关联链表
        res.next = head;
        //构建当前交换前置节点
        ListNode pre = res;
        //继续运行条件，可能出现奇数节点链表
        // 0      -> 1     -> 2     -> 3     -> 4 -> 5
        //pre     head     next    temp
        while (pre.next != null && pre.next.next != null) {//前置节点的下一个节点和下一个的下一个节点不能为空
            //1、构建 next 和 temp节点
            ListNode next = head.next;
            ListNode temp = head.next.next;
            //2、进行交换
            pre.next = next;
            next.next = head;
            head.next = temp;
            //结果 0      -> 2     -> 1     -> 3     -> 4 -> 5
            //     pre    next     head    temp
            //重置 per节点和head节点
            pre = head;
            head = head.next;
            //结果 0      -> 2     -> 1     -> 3     -> 4     -> 5
            //                      pre    head      next    temp
        }

        return res.next;
    }

    private static ListNode swapPairs(ListNode head) {
        //前置判断
        if (head == null || head.next == null) {
            return head;
        }
        //   1   ->  2       ->  3           -> 4
        //  head    next    head.next.next
        //先将head 的下一个节点2 拿出来
        ListNode next = head.next;
        //将head.next.next节点之后的链表递归交换后与head做绑定
        head.next = swapPairs(head.next.next);
        //然后将head与next做交换
        next.next = head;

        return next;
    }
}
